⟸ pàgina anterior ⟸
Exercici 6 (Tasca 3).
(pumping lemma)

Seqüències unàries amb forats arbitràriament grans

Sigui \boldsymbol a=(a_1,a_2,a_3,\dots) una seqüència ordenada de nombres naturals. Diem que la seqüència \boldsymbol a té forats arbitràriament grans si per tot n\in \mathbb N hi ha un índex i tal que a_{i+1}>a_i +n.

  1. Demostreu que {\boldsymbol a} té forats arbitràriament grans quan

    1. a_i=2^i
    2. a_i=i^2
    3. a_i és l’i-èsim nombre de Fibonacci
    4. a_i is l’i-èsim nombre primer

  2. Donada una seqüència \boldsymbol a amb forats arbitràriament grans, demostreu que el llenguatge L_{\boldsymbol a}=\{1^{k} \mid k\in \boldsymbol a\} no és regular.

    Proveu a demostrar que L_{\boldsymbol a} no és regular en els dos casos següents abans de demostrar el resultat general: a_i=2^i i a_i=i^2. Això us podria donar idees sobre com procedir en el cas general.

  3. Utilitzant les idees dels apartats anteriors, demostreu que els llenguatges següents no són regulars:

    1. \{0101^201^3\cdots01^n \mid n\in \mathbb N\}
    2. \{1^n \mid n\text{ és parell o primer}\}